package com.zyk.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhangsan
 * @date 2021/4/13 11:46
 */
public class C862 {

    // https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/
    // 暴力尝试
    static public int shortestSubarray(int[] A, int K) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < A.length; i++) {
            int p = process(A, i, K, 0);
            if (p >= 0) {
                ans = Math.min(ans, p - i + 1);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process(int[] A, int i, int K, int pre) {
        if (pre >= K)
            return i - 1;
        if (i == A.length)
            return -1;
        return process(A, i + 1, K, pre + A[i]);
    }

    // 滑动窗口解
    // 维护一个前缀和数组, 返回前缀和>=K 且下标最近的两个距离
    static public int shortestSubarray2(int[] A, int K) {
        int N = A.length;
        long[] P = new long[N+1];
        for (int i = 0; i < N; ++i)
            P[i+1] = P[i] + (long) A[i];

        // Want smallest y-x with P[y] - P[x] >= K
        int ans = N+1; // N+1 is impossible
        Deque<Integer> monoq = new LinkedList(); //opt(y) candidates, as indices of P

        for (int y = 0; y < P.length; ++y) {
            // Want opt(y) = largest x with P[x] <= P[y] - K;
            while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
                monoq.removeLast();
            while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
                ans = Math.min(ans, y - monoq.removeFirst());
            monoq.addLast(y);
        }

        return ans < N+1 ? ans : -1;
    }



    // for test
    public static void main(String[] args) {
        int[] A = {77, 19, 35, 10, -14};
        int K = 19;
        System.out.println(shortestSubarray(A, K));
        System.out.println(shortestSubarray2(A, K));
    }

}
